package com.tgy.topk;

import com.common.sort.tools.Integers;

/**
 * @Author: tgy
 * @Date: 2020-10-19 10:37
 */
public class TopKBFPRT {

    private Integer[] elements;

    private int k;


    public int topK(Integer[] elements, int k) {

        this.elements = elements;
        this.k = k;

        return bfprt(0,elements.length - 1);
    }



    private int bfprt(int begin, int end) {

        middleValOfElements(begin,end);

        int base = elements[begin];
        int left = begin, right = end;
        while (left < right) {

            while (left < right) {

                if (elements[right] > base) {

                    right--;
                }else {

                    elements[left++] = elements[right];
                    break;
                }
            }

            while (left < right) {

                if (elements[left] < base) {

                    left++;
                }else {

                    elements[right--] = elements[left];
                    break;
                }
            }
        }

        if (left != begin) {

            elements[left] = base;
        }

        if (left == elements.length - k) {

            return base;
        }else if (left > elements.length - k) {

            return bfprt(begin, left - 1);
        }else {

            return bfprt(left+1,end);
        }

    }

    private void middleValOfElements(int begin, int end) {

        int i = begin, index = 0;
        for (; i + 4 <= end ; i+=5) {

            insertSort(i,i+4);
            swap(begin + index, i + 2);
            index++;
        }

        if (i <= end && i + 4 > end) {
            insertSort(i,end);
            swap(begin + index,i + ((end - i) >> 1));
            index++;
        }

        if (index == 1) {

            return;
        }

        middleValOfElements(begin,begin + index - 1);
    }

    private void insertSort(int begin,int end) {

        if (end - begin <= 1) {
            return;
        }

        for (int i = begin + 1; i <= end; i++) {

            int e = elements[i];
            int j = i - 1;
            for (; j >= begin; j--) {

                if (e < elements[j]) {

                    elements[j + 1] = elements[j];
                }else {

                    break;
                }
            }

            if (j + 1 != i) {

                elements[j+1] = e;
            }
        }

    }

    private void swap(int i1,int i2) {

        int tmp = elements[i1];
        elements[i1] = elements[i2];
        elements[i2] = tmp;
    }
}
